from DoubleLinkedList import DoubleLinkedList, Node


class FIFOCache(object):

    def __init__(self, capacity):
        """
        param:  capacity: 也是用来设置容量大小的
        param:  map: 定义映射表。加快链表元素的查找速度。
                     key就是 链表key，value就是 node节点本身的引用
        param:  list: 双向链表对象
        param:  size: 当前元素个数
        """
        self.capacity = capacity
        self.map = {}
        self.list = DoubleLinkedList(self.capacity)
        self.size = 0

    
    def get(self, key):
        """ 实现get方法 
            找到返回value， 找不到返回 -1
        """
        node = self.map.get(key, None)
        if not node: return -1

        return node.value


    def put(self, key, value):
        """ 实现put方法
            if 如果已存在：
                则1.更新该节点对应的value，2.将该节点从原位置删除，3.将节点添加到尾部
                （好处是，少了重复创建结点）
            else：不存在就判断是否插入新的
                if 容量已满：
                    需要删除(头部节点, 删除map中的映射)
                添加
        """
        node = self.map.get(key, None)
        if node: 
            # node存在，相当于更新操作，需要删除原来位置，在添加到链表尾
            self.list.remove(node)
            node.value = value
            self.list.append(node)
        else: 
            if self.size == self.capacity:
                node = self.list.pop()
                del self.map[node.key]
                self.size -= 1
            node = Node(key, value)
            self.list.append(node)
            self.map[key] = node
            self.size += 1
        

    def print(self):
        self.list.print()



# 测试
if __name__ == '__main__':
    cache = FIFOCache(2)
    cache.put(1, 1)
    cache.print()
    cache.put(2, 2)
    cache.print()
    print(cache.get(1))
    cache.put(3, 3)
    cache.print()
    print(cache.get(2))
    cache.print()
    cache.put(4, 4)
    cache.print()
    print(cache.get(1))


